package oj_leetcode;

import java.util.Arrays;

public class FindFirstAndLastPositionOfElement {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                int resl = searchRange(nums, left, mid, target, false);
                int resr = searchRange(nums, mid, right, target, true);
                return new int[]{resl, resr};
            }
            if (nums[mid] > target) {
                right = mid  - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{-1, -1};
    }

    public int searchRange(int[] nums, int left, int right, int target, boolean isRight) {
        if (isRight) {
            // 从左到右，第一个不是target的数
            while (left <= right) {
                int mid = (left + right + 1) / 2; // 注意，这里+1，因为要主动向右
                if (nums[right] == target) {
                    return right;
                }
                if (nums[mid] == target) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        } else {
            // 从右到左，第一个不是target的数
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[left] == target) {
                    return left;
                }
                if (nums[mid] == target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return right;
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new FindFirstAndLastPositionOfElement().searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
    }
}
